The present invention relates to a computer graphics system, and more particularly, to a triangle traversing method and a rasterizer adopting the same, in which Phong shading can be efficiently performed.
In computer graphics, the methods for coloring objects can be divided into two types: one where the color value of a pixel at a curved surface of the object is directly calculated (for example, by ray tracing or radiosity) and another where the object is modeled as a polyhedron having constant color values throughout each face. In other words, a smooth surface is approximated as a polyhedron in order to simplify hidden-surface elimination, and shading calculations are employed to restore the surface's smooth appearance.
Shading algorithms such as Gouraud shading and Phong shading have been suggested. In shading, normals are computed at the vertices of each face and approximate the normal to the true surface at the vertex. Each vertex normal is then used to compute a vertex color value. Then, in Gouraud shading, the color values inside the face are linearly interpolated from the vertex color values. Thus, Gouraud shading, although very simple, has deficiencies, for example, Mach band effects. For remedying such deficiencies, Phong shading has been proposed, in which vertex normals instead of vertex shades are linearly interpolated and then the shade at each pixel is determined based on the shading equation. However, Phong shading entails a complex calculation, which leads to difficulty in its hardware implementation. In addition, the software implementation of Phong shading requires an immense amount of processing time. For instance, for a diffused reflection model, the calculation of the color value at any pixel based on its normal according to the following equation (1) requires seven addition operations, six multiplication operations, one division operation, and one square root calculation. ##EQU1##
Here, F denotes a color value; I.sub.d denotes the intensity of a point light source; K.sub.d denotes a coefficient of scattering refection; L denotes a unit normal vector with respect to the surface; and N denotes a unit vector of the surface.
To reduce the amount of the above computation which is required for performing Phong shading, a new algorithm typically called "fast Phong shading" has been proposed by Gary Bishop and David M. Weimer, in which the shading equation is approximated into two terms of a Taylor series. Consequently, by fast Phong shading, the linear interpolation of normals is converted into a quadratic interpolation of shades.
Meanwhile, as the polygon constituting the faces of the polyhedron, a triangle is commonly used in order to obtain high efficiency by reducing needless overhead since, if span data for a polygon (not a triangle) is generated from a geometric processor and applied to a rasterizer, the workload of the geometric processor is so much greater than that of the rasterizer, so that the rasterizer is often idle, which diminishes the system's overall efficiency. Accordingly, it follows that the polygon span data should be converted into triangle span data using the geometric processor for attaining the load distribution.
The amount of rasterizer calculation depends on how the triangle is to be traversed. Therefore, a more efficient traversing method is required, for increasing the speed of the graphics system. To do this, the Pineda algorithm has been proposed to traverse a triangle efficiently. However, this algorithm has a disadvantage in that its control logic is so complex that its hardware implementation is difficult. In addition, this algorithm performs needless calculations which relate to pixels outside the triangle.